package setZeros;
/**
 * @Date 2020/03/27
 * @author 王光浩 
 * @Thinking 为了符合题目要求，使用O（1）的空间复杂度。核心在于：使用遍历过后的元素来作为标记点。
 * @Analysis 时间复杂度O（n^2）,，空间复杂度O（1）
 */
public class MyMethodTwo {
	public void setZeroes(int[][] matrix) {
		boolean first=false; //判断第一行是否需要置0
		for(int i=0;i<matrix.length;i++) {
			for(int j=0;j<matrix[0].length;j++) {
				if(matrix[i][j]==0) {
					if(i==0)first=true;
					else matrix[i][0]=0;  //记录需要置为0的行（将行的第一个置为0）
					matrix[0][j]=0;       //记录需要置为0的列（将列的第一个置为0）
				}
			}
		}
		//先将列置为0（第一列先不动）
		for(int i=1;i<matrix[0].length;i++) {
			if(matrix[0][i]==0) {
				for(int j=1;j<matrix.length;j++)
					matrix[j][i]=0;
			}
		}
		//再将行置为0，第一行先不动
		for(int i=1;i<matrix.length;i++) {
			if(matrix[i][0]==0) {
				for(int j=1;j<matrix[0].length;j++)
					matrix[i][j]=0;
			}
		}
		//判断第一列是否需要置为0
		if(matrix[0][0]==0) {
			for(int i=1;i<matrix.length;i++)
				matrix[i][0]=0;
		}
		//判断第一行是否需要置为0
		if(first) {
			for(int i=1;i<matrix[0].length;i++)
				matrix[0][i]=0;
		}
    }
}
